package com.fs.leetcode.array;

import java.util.Arrays;

/**
 * @author shuai.fang
 * @date：2018-02-05
 * @description：组合排序好的两个数组  升序排列
 */
public class MergeSortedArray {
	public static void main(String[] args) {
		int[] a = {1, 3, 5, 7, 9};
		int[] b = {1, 2, 4, 5, 6, 8, 10, 11};
		int[] mergedArray = mergeSortedArray(a, b);
		System.out.println(Arrays.toString(mergedArray));

		int[] mergedArray2 = mergeSortedArray2(a, b);
		System.out.println(Arrays.toString(mergedArray2));
	}

	/**
	 * 正序排列，这种方法过于繁琐
	 * @param a
	 * @param b
	 * @return
	 */
	public static int[] mergeSortedArray(int[] a, int[] b) {
		int[] newArray = new int[a.length + b.length];
		int lastBIndex = 0;
		int index = 0;
		for (int i = 0; i < a.length; i++) {

			for (int j = lastBIndex; j < b.length; j++) {
				int baDiff = b[j] - a[i];
				if (baDiff < 0) {
					newArray[index++] = b[j];
				} else {
					if (i != a.length - 1) {
						if (b[j] - a[i] == 0) {
							newArray[index++] = b[j];
						} else if (b[j] - a[i] < a[i + 1] - a[i]) {
							newArray[index++] = a[i];
							lastBIndex = j;
							break;
						}
					} else {
						if (b[j] - a[i] < 0) {
							newArray[index ++] = b[j];
						} else {
							newArray[index++] = a[i];
							for (int k = j; k < b.length; k++) {
								newArray[index++] = b[k];
							}
							break;
						}
					}
				}
			}
		}
		return newArray;
	}

	/**
	 * 简单的做法--推荐
	 * @param a
	 * @param b
	 * @return
	 */
	public static int[] mergeSortedArray2(int[] a, int[] b) {
		int[] newArray = new int[a.length + b.length];
		int i = newArray.length - 1;
		int k = a.length - 1;
		int j = b.length -1;
		while (i >= 0) {
			if (k >= 0 && j >= 0) {
				if (a[k] > b[j]) {
					newArray[i] = a[k];
					k--;
				} else {
					newArray[i] = b[j];
					j--;
				}
			} else if (k >= 0) {
				newArray[i] = a[k];
				k--;
			} else if (j >= 0) {
				newArray[i] = b[j];
				j--;
			}
			i--;
		}
		return newArray;
	}
}
